/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package thirdProject;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import org.jgrapht.DirectedGraph;
import org.jgrapht.alg.CycleDetector;
import org.jgrapht.alg.DijkstraShortestPath;
import org.jgrapht.graph.AsUndirectedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;

/**
 *
 * @author asculx
 */
public class GraphUtility {

    public GraphUtility() {
    }

    
    private Point findFirstUnvisited(DirectedGraph<Point, DefaultWeightedEdge> graph,Point source,ArrayList<Point> visited){
        System.out.println("METODO OTTIMIZZAZIONE 1");
        Point p=null;
        Set<Point> points = graph.vertexSet();
        for (Iterator<Point> it = points.iterator(); it.hasNext();) {
            Point point = it.next();
            if(!visited.contains(point)){
                if(p==null){
                    p=point;
                    System.out.println("Punto + Vicino "+p);
                }else if(source.distance(point) < source.distance(p)){
                    p=point;
                }
            }
        }
        return p;
    }
    
    public ArrayList<Point> pathTofirstUnvisited(DirectedGraph<Point, DefaultWeightedEdge> graph, Point source,ArrayList<Point> visited ){
        ArrayList<Point> path;
        Point target=findFirstUnvisited(graph, source, visited);
        path=getMinPath(graph, target, source);
        return path;
    }
    
    public ArrayList<Point> getMinPath(DirectedGraph<Point,DefaultWeightedEdge> graph, Point source,Point target){
        
        System.out.println("SOURCE = "+source+"  TARGET = "+target);
        
        ArrayList<Point> path=new ArrayList<Point>();
        AsUndirectedGraph<Point, DefaultWeightedEdge> graphToCheck;
        graphToCheck = new AsUndirectedGraph<Point, DefaultWeightedEdge>(graph);
        List<DefaultWeightedEdge> edgeList = DijkstraShortestPath.findPathBetween(graphToCheck, source, target);
        for (DefaultWeightedEdge edge : edgeList) {
            path.add(graphToCheck.getEdgeTarget(edge));
        }
        if (path.size() > 0) {
            path.add(graphToCheck.getEdgeSource(edgeList.get(edgeList.size() - 1)));
        }
        System.out.println("PATH DENTRO  : "+path);   
        return path;
    }
    
    public ArrayList<Point> getMooreNeightboor(DirectedGraph<Point,DefaultWeightedEdge> graph, Point vertex){
        ArrayList<Point> retList=new ArrayList<Point>();
        int ymin= vertex.y-1;
        int ymax= vertex.y+1;
        int xmin = vertex.x-1;
        int xmax= vertex.x+1;
        
        int centerX=vertex.x;
        int centerY=vertex.y;
        
        for(int x = xmin ; x <= xmax ; x++){
            for(int y = ymin ; y <= ymax;y++ ){
                if(x!= centerX && y!=centerY){
                    Point tmp =new Point(x,y);
                    if(graph.containsVertex(tmp)){
                        retList.add(tmp);
                    }
                }
            }
        }
        return retList;
    }
    
    public void edgingBlockGraph(DirectedGraph<Point,DefaultWeightedEdge> graph, Point currVertex){
        ArrayList<Point> vertexList=getMooreNeightboor(graph, currVertex);
        System.out.println("vertex List : "+vertexList);
        for (Point point : vertexList) {
            if(!point.equals(currVertex) && graph.containsVertex(point)){ // EVITA il ciclo a se stesso e verifica che i punti siano nel grafo                
                if(!graph.containsEdge(currVertex, point)){
                    graph.addEdge(currVertex, point);
                }   
              if(!graph.containsEdge(point, currVertex)){
                    graph.addEdge(point,currVertex);
                }
            }
        } 
    }
    
    
    
        
    public boolean findcircle(DirectedGraph<Point,DefaultWeightedEdge> graph){
        boolean isCircled=false;
        CycleDetector<Point,DefaultWeightedEdge> cycle=new CycleDetector<Point, DefaultWeightedEdge>(graph);
        if(cycle.detectCycles() && cycle.findCycles().size() >= 4){
                System.out.println("HO TROVATO UN CICLO ");
                System.out.println(cycle.findCycles());
        }
        return isCircled;
    }
    
    
}
